<?php
//include_once("class_segment.php");
//include_once("class_unit.php");
//include_once("inc_str.php");
//include_once("inc_array.php");

class Tool_segment_light{

  public static function get_char(&$_str,$_offset){
    return mb_substr($_str,$_offset,1);
  }

  public static function tostring(&$_seg,&$_str){
    return mb_substr($_str,$_seg[0],$_seg[1]);
  }
 
  public static function tostringpartial(&$_seg,&$_str,$_len){
    return mb_substr($_str,$_seg[0],$_len);
  }

  public static function totruesegment(&$_seg,&$_str){
    return new Segment($_str,$_seg[0],$_seg[1]);
  }

  public static function get_same_prefix(&$_seg1,&$_seg2,&$_str1,&$_str2){
    $len=min($_seg1[1],$_seg2[1]);
    for($i=0;$i<$len &&
        (self::get_char($_str1,$i+$_seg1[0])==self::get_char($_str2,$i+$_seg2[0]));$i++);
    return $i;
  }

  public static function does_include_strict(&$_seg1,&$_seg2){
    $offset_start=$_seg2[0];
    $offset_end=$offset_start+$_seg2[1];
    $start=$_seg1[0];
    $end=$start+$_seg1[1];
    return ($end>=$offset_end and $start<=$offset_start) ? true : false;
  }

//tri par longueur
 public static function usort_len($i,$j){
  if($i[1] < $j[1]) return -1;
  else return ($i[1] > $j[1]) ? 1 : 0;
 }

//tri par position
 public static function usort_offset($i,$j){
  if($i[0] < $j[0]) return -1;
  else return ($i[0] > $j[0]) ? 1 : 0;
 }

}

class suffixarray{
  private $array_str=array();
  private $array_suffix=array();
  private $array_repeated=array();
  private $array_distrib=array();

  public function __construct(){}

  public function __add_str(&$_str){
    $id_str=array_push($this->array_str,$_str)-1;
    $str_len=mb_strlen($_str);
    for($i=0;$i<$str_len;$i++)
      $this->array_suffix[]=array($i,$str_len-$i,$id_str);
  }

  public function usort_segment(&$_seg1,&$_seg2){
    return strcmp(
      Tool_segment_light::tostring($_seg1,$this->array_str[$_seg1[2]]),
      Tool_segment_light::tostring($_seg2,$this->array_str[$_seg2[2]])
    );
  }

  public function __init(){
//    print_r($this);
    $start=microtime(true);
    usort($this->array_suffix,array($this,"usort_segment"));
    $time=microtime(true)-$start;
    echo "1 : $time\n";
    $start=microtime(true);
    $res=$this->step2();
    $time=microtime(true)-$start;
    echo "2 : $time\n";
    $start=microtime(true);
    $this->step3($res);
    $time=microtime(true)-$start;
    echo "3 : $time\n";
    $start=microtime(true);
    $this->step4();
    $time=microtime(true)-$start;
    echo "4 : $time\n";
    $start=microtime(true);
    $this->step5();
    $time=microtime(true)-$start;
    echo "5 : $time\n";
    return $this->array_distrib;
  }


 private function step2(){
  $lcps=array();
  $len=count($this->array_suffix);
  for($i=0;$i<$len-1;$i++){
   $seg1=$this->array_suffix[$i];
   $seg2=$this->array_suffix[$i+1];
   $lcps[$i]=Tool_segment_light::get_same_prefix($seg1,$seg2,$this->array_str[$seg1[2]],$this->array_str[$seg2[2]]);
  }
  $lcps[$i]=0;
  return $lcps;
 }

 private function step3($_lcps){
  $res=$res2=$return=array();
  $max=count($_lcps);
  $valid=array();
//  print_r($this->array_suffix);
//  print_r($_lcps);
/*  
  foreach($this->array_suffix as $suffix){
    echo tool_segment_light::tostringpartial($suffix,$this->array_str[$suffix[2]],10)." ";
    foreach($suffix as $inf){
      echo "$inf ";
    }
    echo "\n";
  }
  die();
*/
/*
  foreach($this->array_suffix as $suffix){
    echo "\"".tool_segment_light::tostringpartial($suffix,$this->array_str[$suffix[2]],20)."\"";
    //echo "\"".tool_segment_light::get_char($this->array_str[$suffix[2]],$suffix[0])."\"";
    echo "\n";
  }
  die();
*/
  for($i=0;$i<$max-1;$i++){
    $cpt1=$cpt2=$i;
    if($_lcps[$i]>0){
      $id_str_i=$this->array_suffix[$i][2];
      if(!isset($res["$i-$id_str_i-$_lcps[$i]"])){
       $res["$i-$id_str_i-$_lcps[$i]"]=1;
       $clone=array($this->array_suffix[$i][0],$_lcps[$i],$id_str_i,$i);
       $str=tool_segment_light::tostring($clone,$this->array_str[$id_str_i]);
       $this->array_repeated[$str][]=$clone;
      }
      do{
        $cpt1++;
        $id_str_cpt1=$this->array_suffix[$cpt1][2];
        if(!isset($res["$cpt1-$id_str_cpt1-$_lcps[$i]"])){
         $res["$cpt1-$id_str_cpt1-$_lcps[$i]"]=1;
         $clone=array($this->array_suffix[$cpt1][0],$_lcps[$i],$id_str_cpt1,$cpt1);
         $str=tool_segment_light::tostring($clone,$this->array_str[$id_str_cpt1]);
         $this->array_repeated[$str][]=$clone;
        }
      }while($_lcps[$i]<=$_lcps[$cpt1]);

      $cpt2--;
      while($_lcps[$i]<=$_lcps[$cpt2]){
       $id_str_cpt2=$this->array_suffix[$cpt2][2];
       if(!isset($res["$cpt2-$id_str_cpt2-$_lcps[$i]"])){
        $res["$cpt2-$id_str_cpt2-$_lcps[$i]"]=1;
        $clone=array($this->array_suffix[$cpt2][0],$_lcps[$i],$id_str_cpt2,$cpt2);
        $str=tool_segment_light::tostring($clone,$this->array_str[$id_str_cpt2]);
        $this->array_repeated[$str][]=$clone;
       }
       $cpt2--;
      }
    }
  }
  unset($res);
/*
  foreach($this->array_repeated as $str=>$array){
    echo $str;
    echo "\n";
  }
  die();
*/
  $start=microtime(true);
  foreach($this->array_repeated as $s=>$array){
    usort($array,array($this,"step3_usort_new"));
//    echo $s;
//    echo "\n";
  }
//  print_r($this->array_repeated);
//  die();

  usort($this->array_repeated,array($this,"usort_rev_array"));
//  print_r($this->array_repeated);
//  die();
  $time=microtime(true)-$start;

//  echo "3.X1 : $time\n";
 }



 private function step3_usort_new($i,$j){
//  if($i[3]<$j[3]) return -1;
//  elseif($i[3]>$j[3])return 1;
  if($i[2]<$j[2]) return -1;
  elseif($i[2]>$j[2]) return 1;
  elseif($i[1]<$j[1]) return -1;
  elseif($i[1]>$j[1]) return 1;
  else return $i[0]-$j[0];
 }


//tri des suffix
 private function usort_rev($_seg1,$_seg2){
   $lenmin=min($_seg1[1],$_seg2[1]);
   $oi=$_seg1[1]+$_seg1[0]-1;
   $oj=$_seg2[1]+$_seg2[0]-1;
   while($lenmin and
         (Tool_segment_light::get_char($this->array_str[$_seg1[2]],$oi)==Tool_segment_light::get_char($this->array_str[$_seg2[2]],$oj))){
    --$lenmin;--$oi;--$oj;
   }
   if(!$lenmin){return $_seg1[1]-$_seg2[1];}
   else{
     return (Tool_segment_light::get_char($this->array_str[$_seg1[2]],$oi)<Tool_segment_light::get_char($this->array_str[$_seg2[2]],$oj))? -1 : 1;
   }
 }

 private function usort_rev_array($_array_seg1,$_array_seg2){
  return $this->usort_rev($_array_seg1[0],$_array_seg2[0]);
 }

 private function step4(){
  $max=count($this->array_repeated);
  for($i=0;$i<$max-1;$i++){
   if(tool_segment_light::does_include_strict($this->array_repeated[$i+1][0],$this->array_repeated[$i][0])
      and count($this->array_repeated[$i])==count($this->array_repeated[$i+1]))
      unset($this->array_repeated[$i]);
  }
 }

 private function step5(){
  foreach($this->array_repeated as $repeated){
   $str=tool_segment_light::tostring($repeated[0],$this->array_str[$repeated[0][2]]);
   foreach($repeated as $segment){
    $this->array_distrib[$str][]=tool_segment_light::totruesegment($segment,$this->array_str[$segment[2]]);
   }
  }
  ksort($this->array_distrib);
 }


}

?>
